--[[
	HENRIQUE "Nican" POLIDO
	November 02, 2010
	Homework 2
]]--

-- utility to raise an error 
-- on an array that is *not* properly sorted
-- between start and finish.  
-- s is a string to use to inform the user 
-- about who is to blame.  

function assert_sorted (a,start,finish,s) 
   local last = a[start] 

   for i = start+1, finish do 
      assert((last <= a[i]), 
	     string.format("%s: value %d at %d\n", s, a[i], i)) 
      last = a[i]
   end
end 

-- seed the random number generator.  
-- Probably overkill, but we only do it once (:-) 

function set_randomseed () 
   local d = os.date() .. os.clock () 
   local t = {string.byte(d,1,string.len(d))}
   local c = 1 
   for i = 1, #t do 
      _,c = math.modf(math.exp((math.log(t[i]*c))/2))
   end 
   math.randomseed (math.modf(c*10000000000000))
end

set_randomseed ()

-- fill a table of length len
-- with integers randomly chosen  
-- between lower bound lb and upper bound ub (inclusive).  

function random_table (lb, ub, len) 
   local t = {} 
   for i = 1,len do 
      t[i] = math.random(lb,ub)
   end
   return t
end 

function insertion_sort (given)
   local flag
   local insert = table.insert
   local t = {} 
   t[1] = given[1] 

   -- put each remaining value in given 
   -- somewhere in t.  

   -- Note use of # to return length of a gap-free array.  
   -- table.insert inserts the value at the position j, 
   -- and shifts the rest of the array upward.  

   for i=2, #(given) do 
      for j = 1, #t do 

	 flag=false 

	 -- if it's less than this entry in t
	 -- put it here

	 if given[i]<t[j] 
	 then flag=true 
	    insert(t,j,given[i]) 
	    break
	 end
      end

      -- if it wasn't less than any value in t,
      -- put it at the end.  

      -- table.insert(t,v) with no index j puts v at #t+1.  

      if not(flag) then insert(t,given[i]) end 
   end
   return t 
end 

function sort_random (lb, ub, len)
   local o = random_table (lb, ub, len)
   local n 

   n = insertion_sort(o) 

   return n
end

--[[ 

CMerge: 

Assume that a1 is sorted, and a2 is sorted.

Return a table r containing their joint 
content, globally sorted.  

That is, make sure the entries in 
a1 are in the right spots versus the
entries in a2.  

Called CMerge because it does a lot of copying.  

--]]
function cmerge (a1,a2) 
   local r = {} 

   local a1_len = #(a1)
   local a2_len = #(a2)

   local i1 = 1 
   local i2 = 1
   
   --Reducing the lookup time of table.insert can have some performance increase
   local insert = table.insert

   -- as long as either array is not fully inserted into r ... 

   while i1 <= a1_len or i2 <= a2_len do 
      
      if i1 <= a1_len and i2 <= a2_len 
      -- if both arrays still have values remaining, 
      -- insert the lesser of the two values 
      then if a1[i1] <= a2[i2] 
	 then
	    insert(r, a1[i1]); 
	    i1 = i1+1
	 else 
	    insert(r, a2[i2]); 
	    i2 = i2+1
	 end
      else
	 -- otherwise, whichever one still has values, 
	 -- take the next value from it
	 if i1 <= a1_len 
	 then 
	    insert(r, a1[i1]); 
	    i1 = i1+1
	 else 
	    insert(r, a2[i2]); 
	    i2 = i2+1
	 end
      end
   end
   return r
end

function split_array (a) 
   local mid = math.floor((#a)/2)
   local insert = table.insert
   local t1 = {} 
   local t2 = {} 

   -- copy first half to t1 

   for i = 1, mid do 
      insert(t1, a[i])
   end
   
   -- copy second half to t2 

   for i = mid+1, #a do 
      insert(t2, a[i])
   end

   -- return em both 

   return t1,t2
end 

function cmerge_sort (a) 
   if #a <= 1 
   then
      return a 
   else
      local t1,t2 = split_array(a)

      -- solve both subproblems recursively,
      -- then cmerge the sorted results 

      return cmerge(cmerge_sort(t1),
		    cmerge_sort(t2))
   end
end 

function cmerge_sort_random (lb, ub, len)
   local o = random_table (lb, ub, len)
   local n 

   n = cmerge_sort(o) 
   assert_sorted(n,1,#n,"cmerge, unsorted result")
   return n
end

--Part 1 of the homework
function measured_sort_1()
	
	local t0 = os.clock()
	
	insertion_sort( random_table(1,1000,10000) )
	
	local t1 = os.clock()
	return t1-t0

end
--print( measured_sort_1() ) --Output: 2.369

--Part 2 of the homework
function  measured_sort_vec( repetitions, lb, ub, length )
	
	local timings = {}
	
	for i=1, repetitions do
	
		local t0 = os.clock()
	
		insertion_sort( random_table(lb, ub, length) )
	
		table.insert(timings, os.clock() - t0 )
		
	end
	
	return timings
end

--Part 3 of the homework
function math.averge( tbl )
	local sum = 0
	
	for _, val in ipairs( tbl ) do
		sum = sum + val
	end
	
	return sum / #tbl	
end

function averge_measured_sort_vec( reps )
	return math.averge( measured_sort_vec( reps, 1, 1000, 10000) )
end

--print( averge_measured_sort_vec( 20 ) ) --Output: 2.37025
--Yes, depended on the size and organization of the incoming dataset, the difference between algorithms and benchmarks can vary a large quantatity

--Part 4 of the homework
function  measured_cmerge_sort_vec( repetitions, lb, ub, length )
	
	local timings = {}
	
	for i=1, repetitions do
	
		local t0 = os.clock()
	
		cmerge_sort( random_table(lb, ub, length) )
	
		table.insert(timings, os.clock() - t0 )
		
	end
	
	return timings
end

function averge_cmerge_sort_vec( reps )
	return math.averge( measured_cmerge_sort_vec( reps, 1, 1000, 10000) )
end
--print( averge_cmerge_sort_vec( 20 ) ) --Output: 0.0942


--Part 5 of the homework
function graph_insertion_step( start, reps, step )

	local length = start

	print("Insertion sort: ")
	
	for i=1, reps do
		
		local AvgTime = math.averge( measured_sort_vec( 2, 100, 10000, length ) )
		
		print("\t" .. length .. "\t" .. AvgTime )
		
		length = length + step
	
	end

end 
--graph_insertion_step( 100, 40, 1000 )



--Part 5 of the homework
function graph_merge_step( start, reps, step )

	local length = start

	print("Insertion sort: ")
	
	for i=1, reps do
		
		local AvgTime = math.averge( measured_cmerge_sort_vec( 2, 100, 10000, length ) )
		
		print("\t" .. length .. "\t" .. AvgTime )
		
		length = length + step
	
	end

end 
--graph_merge_step( 100, 40, 3000 )


print( math.averge( measured_cmerge_sort_vec( 1, 1, 1000, 1000000) ) ) --11.478
print( math.averge( measured_sort_vec( 1, 1, 1000, 1000000) ) ) --23745.382

